package com.beautiful.xin.map;

/**
 * @author xuqingxin 2021/7/22 11:04 上午
 */
public class MapTest {

    /**   *************************************** putVal 方法解析  ***************************************
     *
     * <pre>
     * final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
     *         //声明了一个局部变量 tab,局部变量 Node 类型的数据 p,int 类型 n,i
     *         Node<K, V>[] tab;
     *         Node<K, V> p;
     *         int n, i;
     *         //首先将当前 hashmap 中的 table(哈希表)赋值给当前的局部变量 tab,然后判断tab 是不是空或者长度是不是 0,实际上就是判断当前 hashmap 中的哈希表是不是空或者长度等于 0
     *         if ((tab = table) == null || (n = tab.length) == 0)
     *             //如果是空的或者长度等于0,代表现在还没哈希表,所以需要创建新的哈希表,默认就是创建了一个长度为 16 的哈希表
     *             n = (tab = resize()).length;
     *         //将当前哈希表中与要插入的数据位置对应的数据取出来,(n - 1) & hash])就是找当前要插入的数据应该在哈希表中的位置,如果没找到,代表哈希表中当前的位置是空的,否则就代表找到数据了, 并赋值给变量 p
     *         if ((p = tab[i = (n - 1) & hash]) == null)
     *             tab[i] = newNode(hash, key, value, null);//创建一个新的数据,这个数据没有下一条,并将数据放到当前这个位置
     *         else {//代表要插入的数据所在的位置是有内容的
     *             //声明了一个节点 e, 一个 key k
     *             Node<K, V> e;
     *             K k;
     *             if (p.hash == hash && //如果当前位置上的那个数据的 hash 和我们要插入的 hash 是一样,代表没有放错位置
     *                     //如果当前这个数据的 key 和我们要放的 key 是一样的,实际操作应该是就替换值
     *                     ((k = p.key) == key || (key != null && key.equals(k))))
     *                 //将当前的节点赋值给局部变量 e
     *                 e = p;
     *             else if (p instanceof TreeNode)//如果当前节点的 key 和要插入的 key 不一样,然后要判断当前节点是不是一个红黑色类型的节点
     *                 e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);//如果是就创建一个新的树节点,并把数据放进去
     *             else {
     *                 //如果不是树节点,代表当前是一个链表,那么就遍历链表
     *                 for (int binCount = 0; ; ++binCount) {
     *                     if ((e = p.next) == null) {//如果当前节点的下一个是空的,就代表没有后面的数据了
     *                         p.next = newNode(hash, key, value, null);//创建一个新的节点数据并放到当前遍历的节点的后面
     *                         if (binCount >= TREEIFY_THRESHOLD - 1) // 重新计算当前链表的长度是不是超出了限制
     *                             treeifyBin(tab, hash);//超出了之后就将当前链表转换为树,注意转换树的时候,如果当前数组的长度小于MIN_TREEIFY_CAPACITY(默认 64),会触发扩容,我个人感觉可能是因为觉得一个节点下面的数据都超过8 了,说明 hash寻址重复的厉害(比如数组长度为 16 ,hash 值刚好是 0或者 16 的倍数,导致都去同一个位置),需要重新扩容重新 hash
     *                         break;
     *                     }
     *                     //如果当前遍历到的数据和要插入的数据的 key 是一样,和上面之前的一样,赋值给变量 e,下面替换内容
     *                     if (e.hash == hash &&
     *                             ((k = e.key) == key || (key != null && key.equals(k))))
     *                         break;
     *                     p = e;
     *                 }
     *             }
     *             if (e != null) { //如果当前的节点不等于空,
     *                 V oldValue = e.value;//将当前节点的值赋值给 oldvalue
     *                 if (!onlyIfAbsent || oldValue == null)
     *                     e.value = value; //将当前要插入的 value 替换当前的节点里面值
     *                 afterNodeAccess(e);
     *                 return oldValue;
     *             }
     *         }
     *         ++modCount;//增加长度
     *         if (++size > threshold)
     *             resize();//如果当前的 hash表的长度已经超过了当前 hash 需要扩容的长度, 重新扩容,条件是 haspmap 中存放的数据超过了临界值(经过测试),而不是数组中被使用的下标
     *         afterNodeInsertion(evict);
     *         return null;
     *     }
     *
     * </pre>
     */


    /***************************************** resize 方法解析  ***************************************
     *
     * <pre>
     * 	// 这个扩容方法就是
     * 	//   1、找到新的容量大小和新的threshold大小
     * 	//   2、把旧的数据全部复制到新的数组中去
     * 	final Node<K,V>[] resize() {
     *         Node<K,V>[] oldTab = table;
     *         int oldCap = (oldTab == null) ? 0 : oldTab.length;
     *         int oldThr = threshold;
     *         int newCap, newThr = 0;
     * 	       // 非第一次扩容
     *         if (oldCap > 0) {
     *             if (oldCap >= MAXIMUM_CAPACITY) {
     *                 threshold = Integer.MAX_VALUE;
     *                 return oldTab;
     *             }
     *             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
     *                 newThr = oldThr << 1; // double threshold
     *         }
     * 	       // 使用初始化容量或初始化容量+初始化加载因子参数的构造方法，第一次进入扩容
     *         else if (oldThr > 0){
     * 		       newCap = oldThr;
     *        }
     *         // 使用空参构造方法第一次扩容进入，使用参数为map的构造方法，第一次也会进入这个扩容方法
     *         else {
     *             newCap = DEFAULT_INITIAL_CAPACITY;
     *             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
     *         }
     * 	       // 使用初始化容量或初始化容量+初始化加载因子参数的构造方法，第一次进入扩容
     *         if (newThr == 0) {
     *             float ft = (float)newCap * loadFactor;
     *             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
     *         }
     *         threshold = newThr;
     *         @SuppressWarnings({"rawtypes","unchecked"})
     *             Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
     *         table = newTab;
     * 	       // 把旧的数据全部复制到新的数组中去
     *         if (oldTab != null) {
     * 			//
     *
     *         }
     *         return newTab;
     *     }
     *
     *    5、总结（面试的时候：请你说一下HashMap的扩容）：
     *
     *    HashMap底层数据结构是 数组 + 链表 + 红黑树
     *    真正的数据是存储在链表中的，链表的长度是无限的。所以这时候就引入一个变量 threshold
     *    当第一次向map里面添加数据，或添加完数据后的大小，大于 threshold的大小，这时候就会进行扩容
     *    先说一下非第一次扩容，这个相对简单点
     *        1、如果当前的容量大小，大于等于HashMap规定的最大容量的话，直接让threshold等于Integer的最大值，就可以了。
     *        2、一般情况当前数组长度是不会大于最大值的，所以这时候新的数组长度等于旧数组的2倍。如果新的数组长度小于HashMap规定的最大值，并且旧的数组长度也大于等于HashMap规定的默认大小容量大小（16），那么threshold扩大2倍，否则不变
     *    非第一次扩容
     *        1、HashMap，有四个构造方法。空参构造方法的threshold变量是0，其它构造方法threshold都有初始值。
     *        2、当旧的threshold大于0的时候，新的数组容量大小就等于旧的threshold大小。新的threshold大小等于加载因子新的数组大小。
     *        3、当旧的threshold不大于0的时候，新的数组大小就等于默认的大小（16），新的threshold大小，就等于默认的容量大小默认的加载因子大小
     *    上面已经得出了新的容量大小和新的threshold的大小，后面只需要用新容量大小创建一个数组，把旧数组的内容复制进去就好了。
     *
     * </pre>
     *
     */
}
